package com.lazycat.leetcode.editor.cn;
//2023-06-08 11:02:33
//你是一位施工队的工长，根据设计师的要求准备为一套设计风格独特的房子进行室内装修。 
//
// 房子的客厅大小为 n x m，为保持极简的风格，需要使用尽可能少的 正方形 瓷砖来铺盖地面。 
//
// 假设正方形瓷砖的规格不限，边长都是整数。 
//
// 请你帮设计师计算一下，最少需要用到多少块方形瓷砖？ 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：n = 2, m = 3
//输出：3
//解释：3 块地砖就可以铺满卧室。
//     2 块 1x1 地砖
//     1 块 2x2 地砖 
//
// 示例 2： 
//
// 
//
// 输入：n = 5, m = 8
//输出：5
// 
//
// 示例 3： 
//
// 
//
// 输入：n = 11, m = 13
//输出：6
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 13 
// 1 <= m <= 13 
// 
//
// Related Topics 动态规划 回溯 👍 136 👎 0

import com.fzy.test.leetcode348.Main;

class TilingARectangleWithTheFewestSquares {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new TilingARectangleWithTheFewestSquares().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int ans;
    public int tilingRectangle(int n, int m) {
        ans = Math.max(m,n);
        boolean[][] visit = new boolean[n][m];
        dfs(0,0,visit,0);
        return ans;
    }


    private void dfs(int x,int y,boolean[][] visit,int cnt){
        int n = visit.length;
        int m = visit[0].length;

        if(cnt >= ans){
            return;
        }
        if(x >= n){
            ans = cnt;
            return;
        }
        if(y>=m){
            dfs(x+1, 0, visit, cnt);
            return;
        }

        if(visit[x][y]){
            dfs(x,y+1,visit,cnt);
            return;
        }

        for(int k = Math.min(n-x,m-y);k>=1 && isAvailable(visit,x,y,k);k--){

            //将长度为k的正方形区域标记覆盖
            fillUp(visit,x,y,k,true);
            //跳过k个位置开始检测
            dfs(x,y+k,visit,cnt+1);
            fillUp(visit,x,y,k,false);
        }
    }

    private boolean isAvailable(boolean[][] visit,int x,int y,int k){
        for(int i = 0;i<k;i++){
            for(int j = 0;j<k;j++){
                if(visit[x+i][y+j]){
                    return false;
                }
            }
        }
        return true;
    }

    private void fillUp(boolean[][] rect,int x,int y,int k,boolean falg){
        for(int i = 0;i<k;i++){
            for(int j = 0;j<k;j++){
                rect[x+i][y+j] = falg;
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}